Saint‑Exupéry ruler

In [1]:

import pulp 

In [2]:

ruler = [i for i in range(21)]

In [3]:

# create problem
prob = pulp.LpProblem("ruler", pulp.LpMinimize)

# x[i]=1 <=> mark on unit i
x = pulp.LpVariable.dicts("x",ruler,cat=pulp.LpBinary)
# y[i][j]=1 <=> mark on units i and j
y = pulp.LpVariable.dicts("y",(ruler,ruler),cat=pulp.LpBinary)

# minimize number of marks
prob+= pulp.lpSum(x)

for i in ruler:
    for j in ruler:
        if j>i:
            prob+= y[i][j]<= x[i]
            prob+= y[i][j]<= x[j]
            prob+= x[i]+x[j] <= y[i][j]+1

for k in ruler:
    if k>0:
        prob+= pulp.lpSum(y[i][j] for i in ruler for j in ruler if j>i if j-i==k)>=1, "length_%s"%k

# match initial conditions
prob+= x[1]==1
prob+= x[4]==1
prob+= x[6]==1

In [4]:

prob.solve()

1

In [5]:

print("mark")
print("----")
for i in ruler:
    if pulp.value(x[i])>0.9:
        print(i)

mark
----
0
1
4
6
11
18
19
20

In [6]:

print("length -> endpoints")
print("-------------------")
for k in ruler:
    if k>0:
        for i in ruler:
            for j in ruler:
                if j>i and j-i==k:
                    if pulp.value(y[i][j])>0.9:
                        print(k,"->",j,i)

length -> endpoints
-------------------
1 -> 1 0
1 -> 19 18
1 -> 20 19
2 -> 6 4
2 -> 20 18
3 -> 4 1
4 -> 4 0
5 -> 6 1
5 -> 11 6
6 -> 6 0
7 -> 11 4
7 -> 18 11
8 -> 19 11
9 -> 20 11
10 -> 11 1
11 -> 11 0
12 -> 18 6
13 -> 19 6
14 -> 18 4
14 -> 20 6
15 -> 19 4
16 -> 20 4
17 -> 18 1
18 -> 18 0
18 -> 19 1
19 -> 19 0
19 -> 20 1
20 -> 20 0

In [7]:

import plotly.express as px
import pandas as pd

def make_ruler(
    start=0, end=10, ticks=None,
    ruler_height=1.0, tick_height=0.7,
    label_offset=-0.15, label_size=36,
    bg_color="#e6e6e6", border_color="black",
    border_thickness=6, tick_width=6,
    width_px=1000, height_px=220
):
    if ticks is None:
        ticks = list(range(int(start), int(end)+1))

    base = pd.DataFrame({"x": [], "y": []})
    fig = px.scatter(base, x="x", y="y")

    # Body
    fig.add_shape(
        type="rect",
        x0=start, x1=end,
        y0=0, y1=ruler_height,
        fillcolor=bg_color,
        line=dict(color=border_color, width=border_thickness),
        layer="below"
    )

    # Ticks + labels
    for x in ticks:
        fig.add_shape(
            type="line",
            x0=x, x1=x,
            y0=ruler_height, y1=ruler_height - tick_height,
            line=dict(color=border_color, width=tick_width)
        )
        fig.add_annotation(
            x=x, y=label_offset,
            text=str(x),
            showarrow=False,
            font=dict(size=label_size, color=border_color),
            align="center",
            yanchor="top"
        )

    pad = max((end - start) * 0.02, 0.2)
    fig.update_layout(
        width=width_px, height=height_px,
        margin=dict(l=20, r=20, t=10, b=10),
        plot_bgcolor="white",
    )
    fig.update_xaxes(range=[start - pad, end + pad],
                     showgrid=False, showticklabels=False,
                     visible=False, fixedrange=True)
    fig.update_yaxes(range=[label_offset - 0.8, ruler_height + 0.3],
                     showgrid=False, showticklabels=False,
                     visible=False, fixedrange=True)
    return fig

# Example
fig = make_ruler(start=0, end=ruler[-1], ticks=[i for i in ruler if pulp.value(x[i])>0.9])
fig.show()